package com.breeze.leetcode.middle;

import java.util.Arrays;

/**
 * @url <a href="https://leetcode.cn/problems/where-will-the-ball-fall">1706. 球会落何处</a>
 * @author yangzh
 * @date 2025/2/15
 */
public class T1706WhereWillTheBallFall {

    public static void main(String[] args) {
        int[][] grid = {{1,1,1,-1,-1},{1,1,1,-1,-1},{-1,-1,-1,1,1},{1,1,1,1,-1},{-1,-1,-1,-1,-1}};
        T1706WhereWillTheBallFall solution = new T1706WhereWillTheBallFall();
        int[] result = solution.findBall(grid);
        System.out.println(Arrays.toString(result));
    }

    public int[] findBall(int[][] grid) {
        int[] result = new int[grid[0].length];

        for (int i = 0; i < result.length; i++) {
            result[i] = dfs(0, i, false, grid);
        }

        return result;
    }

    /**
     * dfs查询
     * @param i 一维坐标
     * @param j 二维坐标
     * @param state 球的状态，false代表在单元格的上半部分，true代表在单位格的下半部分
     * @param grid 二维网格
     * @return 该坐标的结果
     */
    private int dfs(int i, int j, boolean state, int[][] grid) {
        int current = grid[i][j];
        if (i == grid.length - 1 && state) {
            return j;
        }

        if (!state && ((j == 0 && current == -1) || (j == grid[i].length - 1 && current == 1))) {
            return -1;
        }

        // 如果球在上半部分就平行移动，在下半部分就向下移动
        if (state) {
            return dfs(i + 1, j, false, grid);
        } else {
            // 当\/的情况下，球无法下落
            if (current != grid[i][j + current]) {
                return -1;
            }
            return dfs(i, j + current, true, grid);
        }
    }
}
